package _go

/*面试题 02.04. 分割链表
难度
中等

59

收藏

分享
切换为英文
接收动态
反馈
编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。

示例:

输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8
通过次数20,331提交次数30,985*/

// 两个链表记录大于等于 和小于  然后拼接连个链表
func partition(head *ListNode, x int) *ListNode {
	s := &ListNode{}
	sm := s
	b := &ListNode{}
	bm := b

	for head != nil {
		if head.Val >= x {
			b.Next = head
			b = b.Next
		} else {
			s.Next = head
			s = s.Next
		}
		head = head.Next
	}
	b.Next = nil
	s.Next = bm.Next
	return sm.Next
}
